package com.echo.boot.structure.linearlist.linked.single;

import com.echo.boot.structure.linearlist.list.MyAbstractList;

/**
 * Created with IntelliJ IDEA
 * Created By CQ
 * Date: 2020/4/29
 * Time: 21:48
 * 单向链表
 * 哈希表用的是单向链表
 * 边界是否符合条件 index = 0; index = size - 1; index = size;
 *
 * @author Administrator
 */
public class MySingleLinkedList<E> extends MyAbstractList<E> {

    private Node<E> first;

    private static class Node<E> {
        // 每个节点储存里两个元素
        // 一个是元素，一个是下一个节点的地址
        E element;
        Node<E> next;

        public Node(E element, Node<E> node) {
            this.element = element;
            this.next = node;
        }
    }

    @Override
    public void clear() {
        size = 0;
        // 把第一个引用地址去掉,后面的就全部失效
        first.next = null;
    }

    @Override
    public E get(int index) {
        return node(index).element;
    }

    @Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E old = node.element;
        node.element = element;
        return old;
    }

    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        //给空链表添加第一个元素的情况
        if (index == 0) {
            // first 指向的是下一个的节点 first
            first = new Node<>(element, first);
        } else {
            // 获取前一个节点,前一个元素的 next 指向 新的节点
            Node<E> prev = node(index - 1);
            prev.next = new Node<E>(element, prev.next);
        }
        size++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);
        Node<E> node = first;

        // index 等于 0 时,first 指向 first 指向 first.next;
        if (index == 0) {
            first = first.next;
        } else {
            // 被删除节点的前一个节点 指向 被删除节点的 next;
            Node<E> prev = node(index - 1);
            node = prev.next;
            prev.next = node.next;
        }
        size--;
        // 返回被删除的节点
        return node.element;
    }

    @Override
    public int indexOf(E element) {
        if (element == null) {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element == null) {
                    return i;
                }
                node = node.next;
            }
        } else {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (element.equals(node.element)) {
                    return i;
                }
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }


    /**
     * 根据索引找到节点对象
     *
     * @param index
     * @return
     */
    private Node<E> node(int index) {
        rangeCheck(index);
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("size=").append(size);
        builder.append(", [");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                builder.append(", ");
            }
            builder.append(node.element);
            node = node.next;
        }
        builder.append("]");
        return builder.toString();
    }


}
